class SegmentTree:
    def __init__(self, n: int, resource: list[int]):
        self.d = [0 for i in range(n * 4 + 3)]
        self.b = [0 for i in range(n * 4 + 3)]  # 懒标记
        self.a = [0] + resource

    def build(self, s, t, p):
        # 对 [s,t] 区间建立线段树,当前根的编号为 p
        if s == t:
            self.d[p] = self.a[s]
            return
        m = (s + t) >> 1
        self.build(s, m, p * 2)
        self.build(m + 1, t, p * 2 + 1)
        # 递归对左右区间建树
        self.d[p] = self.d[p * 2] + self.d[(p * 2) + 1]

    def update(self, l, r, c, s, t, p):
        # [l, r] 为修改区间, c 为被修改的元素的变化量, [s, t] 为当前节点包含的区间, p为当前节点的编号
        if l <= s and t <= r:
            self.d[p] = self.d[p] + (t - s + 1) * c
            self.b[p] = self.b[p] + c
            return
        # 当前区间为修改区间的子集时直接修改当前节点的值, 然后打标记, 结束修改
        m = s + ((t - s) >> 1)
        if self.b[p] and s != t:
            # 如果当前节点的懒标记非空, 则更新当前节点两个子节点的值和懒标记值
            self.d[p * 2] = self.d[p * 2] + self.b[p] * (m - s + 1)
            self.d[p * 2 + 1] = self.d[p * 2 + 1] + self.b[p] * (t - m)
            # 将标记下传给子节点
            self.b[p * 2] = self.b[p * 2] + self.b[p]
            self.b[p * 2 + 1] = self.b[p * 2 + 1] + self.b[p]
            # 清空当前节点的标记
            self.b[p] = 0
        if l <= m:
            self.update(l, r, c, s, m, p * 2)
        if r > m:
            self.update(l, r, c, m + 1, t, p * 2 + 1)
        self.d[p] = self.d[p * 2] + self.d[p * 2 + 1]

    def getsum(self, l, r, s, t, p):
        # [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p为当前节点的编号
        if l <= s and t <= r:
            return self.d[p]
        # 当前区间为询问区间的子集时直接返回当前区间的和
        m = s + ((t - s) >> 1)
        if self.b[p]:
            # 如果当前节点的懒标记非空, 则更新当前节点两个子节点的值和懒标记值
            self.d[p * 2] = self.d[p * 2] + self.b[p] * (m - s + 1)
            self.d[p * 2 + 1] = self.d[p * 2 + 1] + self.b[p] * (t - m)
            # 将标记下传给子节点
            self.b[p * 2] = self.b[p * 2] + self.b[p]
            self.b[p * 2 + 1] = self.b[p * 2 + 1] + self.b[p]
            # 清空当前节点的标记
            self.b[p] = 0
        ret = 0
        if l <= m:
            ret = self.getsum(l, r, s, m, p * 2)
        if r > m:
            ret = ret + self.getsum(l, r, m + 1, t, p * 2 + 1)
        return ret
